public class Solution {
   public  int InversePairs (int[] arr) {
        int len = arr.length;
        if (len < 2) return 0;
        return reversePairs(arr, 0, len - 1);
    }

    public int reversePairs(int[] arr,int left, int right){
        if (left == right) return 0;
        int mid = (left + right) / 2;
        int leftPairs = reversePairs(arr,left,mid);
        int rightPairs = reversePairs(arr,mid + 1, right);
        int mergeCount = mergeAndCount(arr, left, mid, right);
        return leftPairs + rightPairs + mergeCount;
    }
    public  int mergeAndCount(int[] arr,int left, int mid, int right){
        int count = 0;
        int s1 = left;
        int e1 = mid;
        int s2 = mid + 1;
        int e2 = right;
        int k = 0;
        int[] arr1 = new int[right - left + 1];
        while (s1 <= e1 && s2 <= e2) {
            if (arr[s1] <= arr[s2]) arr1[k++] = arr[s1++];
            else {
                arr1[k++] = arr[s2++];
                count  = (count + mid - s1 + 1) % 1000000007;
            }
        }
        while (s1 <= e1) arr1[k++] = arr[s1++];
        while (s2 <= e2) arr1[k++] = arr[s2++];
        for (int i = 0; i < k; i++) arr[i + left] = arr1[i];
        return count;
    }
}